#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>

const int N = 85, inf = 0x3f3f3f3f;
int n, maxans, map[N][N], lmatch[N], rmatch[N], copy[N], indl[N], indr[N], slack[N],
    pre[N];
bool visl[N], visr[N];

inline void swap(int x) {
  static int tmp;
  while (x) {
    tmp = lmatch[pre[x]];
    rmatch[x] = pre[x];
    lmatch[pre[x]] = x;
    x = tmp;
  }
}

inline void bfs(int s) {
  static int delta;
  memset(visl, 0, sizeof(visl));
  memset(visr, 0, sizeof(visr));
  memset(slack, 0x3f, sizeof(slack));
  std::queue<int> q;
  q.push(s);
  while (true) {
    while (!q.empty()) {
      int u = q.front();
      q.pop(), visl[u] = true;
      for (int v = 1; v <= n; ++v) {
        if (!visr[v]) {
          delta = indl[u] + indr[v] - map[u][v];
          if (!delta) {
            pre[v] = u;
            visr[v] = true;
            if (!rmatch[v]) return swap(v);
            q.push(rmatch[v]);
          } else if (delta < slack[v])
            slack[v] = delta, pre[v] = u;
        }
      }
    }
    delta = inf;
    for (int i = 1; i <= n; ++i)
      if (!visr[i]) delta = std::min(delta, slack[i]);
    for (int i = 1; i <= n; ++i) {
      if (visl[i]) indl[i] -= delta;
      if (visr[i]) indr[i] += delta;
      else
        slack[i] -= delta;
    }
    for (int i = 1; i <= n; ++i)
      if (!visr[i] && !slack[i]) {
        visr[i] = true;
        if (!rmatch[i]) return swap(i);
        q.push(rmatch[i]);
      }
  }
}

inline int KM() {
  static int ans = 0;
  ans = 0;
  memset(lmatch, 0, sizeof(lmatch));
  memset(rmatch, 0, sizeof(rmatch));
  memset(indl, -0x3f, sizeof(indl));
  memset(indr, -0x3f, sizeof(indr));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) indl[i] = std::max(indl[i], map[i][j]);
  for (int i = 1; i <= n; ++i) bfs(i);
  for (int i = 1; i <= n; ++i) ans += indl[i] + indr[i];
  return ans;
}

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P3967 [TJOI2014]匹配.in", "r", stdin);
  freopen("P3967 [TJOI2014]匹配.out", "w", stdout);
#endif
#endif

  scanf("%d", &n);
  memset(map, -0x3f, sizeof(map));
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) scanf("%d", &map[i][j]);
  printf("%d\n", maxans = KM());
  memcpy(copy, rmatch, sizeof(rmatch));
  for (int i = 1; i <= n; ++i)
    for (int j = 1, tmp; j <= n; ++j) {
      if (i != copy[j]) continue;
      tmp = map[i][j];
      map[i][j] = 0;
      if (KM() < maxans) { printf("%d %d\n", i, j); }
      map[i][j] = tmp;
    }
  return 0;
}